/**
 * @file linked_list.hpp
 * @author 逆流 (1171267147@qq.com)
 * @brief
 * @version 0.1
 * @date 2024-10-11
 *
 * @copyright Copyright (c) 2024
 *
 * @section changelog
 * v1.0 实现基本的增删改查功能
 */

#ifndef INC_STL_LINKED_LIST_HPP_
#define INC_STL_LINKED_LIST_HPP_

#include "node.h"
#include "stl/utility/template_type_check.hpp"

namespace stl {

template <typename T>
class LinkedList {
public:
    LinkedList() = default;
    LinkedList(const std::initializer_list<T>& list) : head_(nullptr), length_(0) {
        auto current = head_;
        for (const auto& val : list) {
            auto node = new SingleNode<T>(val);
            if (current == nullptr) {
                head_ = node;
            } else {
                current->next = node;
            }

            current = node;
            length_++;
        }
    }
    ~LinkedList() { Clear(); }

    std::size_t length() const { return length_; }

    bool Empty() const { return nullptr == head_; }

    void Clear() {
        auto current = head_;
        while (current != nullptr) {
            auto next = current->next;
            delete current;
            current = next;
        }
        head_   = nullptr;
        length_ = 0;
    }

    void PushBack(const T& data) { Insert(length_, data); }

    void PushFront(const T& data) { Insert(0, data); }

    /**
     * @brief 将给定的data插入到链表中指定的位置
     * @param index
     * 链表中元素序号.如果index<=0,就插入到链表头部;如果index超过当前链表长度，就插入到链表尾部;否则,插入到指定位置
     * @param data
     */
    void Insert(std::size_t index, const T& data) {
        auto new_node = new SingleNode<T>(data);

        if (index == 0) {
            new_node->next = head_;
            head_          = new_node;
        } else {
            auto previous  = GetNode(index - 1);
            new_node->next = previous->next;
            previous->next = new_node;
        }

        length_++;
    }

    T PopBack() { return Remove(length_ - 1); }
    T PopFront() { return Remove(0); }

    T Remove(std::size_t index) {
        if (index >= length_) {
            throw std::out_of_range("index out of range");
        }
        SingleNode<T>* removed = nullptr;

        if (index > 0) {
            auto previous  = GetNode(index - 1);
            removed        = previous->next;
            previous->next = removed->next;
        } else {
            removed = head_;
            head_   = head_->next;
        }

        auto data = removed->data;
        delete removed;
        length_--;

        return data;
    }

    T& operator[](std::size_t index) {
        if (index < 0 || index >= length_) {
            throw std::out_of_range("index out of range");
        }
        return GetNode(index)->data;
    }

    friend std::ostream& operator<<(std::ostream& ostream, const LinkedList<T>& list) {
        static_assert(has_ostream_operator<T>::value, "Type does not support operator<<");
        for (std::size_t i = 0; i < list.length_; i++) {
            // !list被声明为const，这里只能访问list的const函数
            ostream << list.GetNode(i)->data << " ";
        }
        return ostream;
    }

private:
    /**
     * @brief 获取链表内序号为index的节点
     * @section changelog
     * 24.10.15 修改返回值类型为指针常量，内部已存在的节点可以被删除，但是不应该被改变
     * @return
     */
    SingleNode<T>* GetNode(std::size_t index) const {
        if (index >= length_) {
            throw std::out_of_range("index out of range");
        }
        if (index == 0) {
            return head_;
        }
        auto current = head_;
        for (std::size_t i = 0; i < index; i++) {
            current = current->next;
        }
        return current;
    }

    SingleNode<T>* head_   = nullptr;
    std::size_t    length_ = 0;
};
}  // namespace stl

#endif  // INC_STL_LINKED_LIST_HPP_
